import functools


class Solution(object):
    def palindromePartition(self, s, k):
        @functools.cache
        def find_cost(i, j):
            if i >= j:
                return 0
            if s[i] == s[j]:
                return find_cost(i + 1, j - 1)
            else:
                return 1 + find_cost(i + 1, j - 1)
        @functools.cache
        def dfs(j, t):
            if t == 1:
                return find_cost(0, j)
            else:
                min_cost = float('inf')
                for i in range(t - 2, j):
                    min_cost = min(min_cost, dfs(i, t - 1) + find_cost(i + 1, j))
                return min_cost
        n = len(s)
        return dfs(n - 1, k)